package 栈;

import java.util.ArrayDeque;
import java.util.Deque;

public class No32最长有效括号 {

    /**
     * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
     *
     * 示例 1：
     * 输入：s = "(()"
     * 输出：2
     * 解释：最长有效括号子串是 "()"
     * 示例 2：
     * 输入：s = ")()())"
     * 输出：4
     * 解释：最长有效括号子串是 "()()"
     * 示例 3：
     * 输入：s = ""
     * 输出：0
     *  
     * 提示：
     * 0 <= s.length <= 3 * 104
     * s[i] 为 '(' 或 ')'
     */

    public int longestValidParentheses(String s) {

        /**
         * 用栈存下标,一一配对
         */
        Deque<Integer> stack=new ArrayDeque<>();
        stack.add(-1);
        int max=0;

        for (int i = 0; i < s.length(); i++) {

            if(s.charAt(i)=='('){
                //open
                stack.push(i);
            }else{
                //close
                stack.poll();//只管出,出的就是有效起点,然后只管统计max
                if(stack.isEmpty()){// ')'过多 / 正好用完,则将当前下标当作起点
                    stack.add(i);
                }else{
                    max=Math.max(max,i-stack.peek());
                }
            }

        }

        return max;
    }

}
